template <class Type>
NonFinAut<Type>::NonFinAut()
{
}

template <class Type>
NonFinAut<Type>::NonFinAut(list<Type> &sList, list<Type> &fList)
{
	this->startList = sList;
	this->finishList = fList;
}

template <class Type>
NonFinAut<Type>::NonFinAut(const NonFinAut& other)
{
	initial = other.initial;
	final = other.final;
	size = other.size;
	trans_table = other.trans_table;
	startList = other.startList;
	finishList = other.finishList;
	stateList = other.stateList;
	symbolList = other.symbolList;
	transitionList = other.transitionList;
}

template <class Type>
NonFinAut<Type>::~NonFinAut()
{
}

template <class Type>
bool NonFinAut<Type>::accept(string symbols)
{
	bool check;
	Type begin;
	Type last;
	list<Type>::const_iterator i, l;
	list<Transition<Type>>::const_iterator k;
	for(i = this->startList.begin(); i != this->startList.end(); i++)
	{
		check = true;
		begin = *i;
		for(unsigned int j = 0; j < symbols.length(); j++)
		{
			for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
			{
				if(k->begin == begin && k->symbol == symbols[j])
				{
					begin = k->end;
					last = k->begin;
					break;
				}
			}
			if(k == this->transitionList.end())
			{
				check = false;
				break;
			}
		}
		if(check)
		{
			for(l = this->finishList.begin(); l != finishList.end(); l++)
			{
				for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
				{
					if(k->begin == last && k->symbol == symbols[symbols.length() -1] && k->end == *l)
					{
						return true;
					}
				}
			}
		}
	}
	return false;
}

template <class Type>
void NonFinAut<Type>::addTransition(Type begin, char symbol, Type end)
{
	Transition<Type> transition;
	this->stateList.push_front(begin);
	this->symbolList.push_front(symbol);
	this->stateList.push_front(end);
	stateList.sort();
	stateList.unique();
	symbolList.sort();
	symbolList.unique();
	transition.begin = begin;
	transition.symbol = symbol;
	transition.end = end;
	this->transitionList.push_back(transition);
}

template <class Type>
list<string> NonFinAut<Type>::getLanguage(int size)
{
	list<string> resultList;
	list<Type>::const_iterator i, j;
	list<Transition<Type>>::const_iterator k;
	for(i = this->startList.begin(); i != this->startList.end(); i++)
	{
		for(j = this->finishList.begin(); j != finishList.end(); j++)
		{
			if(*j == *i)
			{
				resultList.push_front("");
			}
		}
		if(size >= 1)
		{
			for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
			{
				if(k->begin == *i)
				{
					list<Type> beginList;
					NonFinAut<Type> nonFinAut;
					list<string> tempList;
					list<string>::const_iterator l;
					
					beginList.push_front(k->end);
					nonFinAut = NonFinAut<Type>(beginList, this->finishList);
					nonFinAut.transitionList = this->transitionList;
					tempList = nonFinAut.getLanguage(size - 1);
					
					for(l = tempList.begin(); l != tempList.end(); l++)
					{
						resultList.push_back(k->symbol + *l);
					}
				}
			}
		}
	}
	return sort(resultList);
}

template <class Type>
list<char> NonFinAut<Type>::getSymbolList()
{
	return this->symbolList;
}

template <class Type>
list<Type> NonFinAut<Type>::getStateList()
{
	return this->stateList;
}

template <class Type>
list<Type> NonFinAut<Type>::getStartList()
{
	return this->startList;
}

template <class Type>
list<Type> NonFinAut<Type>::getFinishList()
{
	return this->finishList;
}

template<class Type>
list<Transition<Type> > NonFinAut<Type>::getTransitionList()
{
	return this->transitionList;
}

template<class Type>
bool NonFinAut<Type>::isEndState(const Type &state)
{
	for(list<Type>::const_iterator iter = finishList.begin(); iter != finishList.end(); iter++)
	{
		if(*iter == state)
		{
			return true;
		}
	}
	return false;
}

template<class Type>
void NonFinAut<Type>::addStartState(const Type &str)
{
	this->startList.push_front(str);
}

template<class Type>
void NonFinAut<Type>::addFinishState(const Type &str)
{
	this->finishList.push_front(str);
}

template <class Type>
void NonFinAut<Type>::printTransitionRules()
{
	list<Type>::const_iterator i;
	list<char>::const_iterator j;
	list<Transition<Type>>::const_iterator k;
	cout << "5-Tupel    :    M = ( {"; 
	for(i = stateList.begin(); i != stateList.end(); i++)
	{
		if(i == (stateList.end()))
		{
			cout << *i;
		}
		else
		{
			cout << *i << ", ";	
		}
	}
	cout << "}, {";
	

	for(j = symbolList.begin(); j != symbolList.end(); j++)
	{
		if(j == symbolList.end())
		{
			cout << *j;
		}
		else 
		{
		cout << *j << ", ";
		}
	}
	cout << "}, {";
	for(i = startList.begin(); i != startList.end(); i++)
	{
		if(i == startList.end())
		{
			cout << *i;
		}
		else
		{
			cout << *i << ", ";
		}
	}
	cout << "}, {";

	for(i = finishList.begin(); i != finishList.end(); i++)
	{
		if(i == finishList.end())
		{
			cout << *i;
		}
		else
		{
			cout << *i << ",";               
		}
	}
	cout << "} )" <<endl<<endl;
	
	for(k = transitionList.begin(); k != transitionList.end(); k++)
	{
		string transition;
		transition += k->begin;
		transition += " >- ";
		transition += k->symbol;
		transition += " -> ";
		transition += k->end;
		if(k == transitionList.begin())
		{
			cout << "transitions:    " << transition << endl;
		}
		else
		{
			cout << "                " << transition << endl;
		}
	}
}

template <class Type>
void NonFinAut<Type>::printLanguage(int count)
{
	list<string> tempList;
	list<string>::const_iterator l;
	list<Transition<Type>>::const_iterator k;
	tempList = getLanguage(count);
	cout <<endl;
	for(l = tempList.begin(); l != tempList.end(); l++)
	{
		if(l == tempList.begin())
		{
			cout << "language:       " << "[" << *l << "]" << endl;
		}
		else
		{
			cout << "                " << "[" << *l << "]" << endl;
		}
	}
}

template <class Type>
void NonFinAut<Type>::rewrite()
{
	list<Transition<Type>> tempList = this->transitionList;
	list<Transition<Type>>::const_iterator i, j, k;
	list<Type>::const_iterator l;
	bool repeat = true;
	for(i = tempList.begin(); i != tempList.end(); i++)
	{
		if(i->symbol == '$')
		{
			for(j = this->transitionList.begin(); j != this->transitionList.end(); j++)
			{
				if(i->end == j->begin)
				{
					Transition<Type> t;
					bool exist = false;
					t.begin = i->begin;
					t.symbol = j->symbol;
					t.end = j->end;
					tempList.push_back(t);
					for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
					{
						if(k->begin == t.begin && k->symbol == t.symbol && k->end == t.end)
						{
							exist = true;
							break;
						}
					}
					if(!exist)
					{
						this->transitionList.push_back(t);
					}
				}
			}
		}
		else 
		{	
			for(j = this->transitionList.begin(); j != this->transitionList.end(); j++)
			{
				if(i->end == j->begin && j->symbol == '$')
				{
					Transition<Type> t;
					bool exist = false;
					t.begin = i->begin;
					t.symbol = i->symbol;
					t.end = j->end;
					tempList.push_back(t);
					for(k = this->transitionList.begin(); k != this->transitionList.end(); k++)
					{
						if(k->begin == t.begin && k->symbol == t.symbol && k->end == t.end)
						{
							exist = true;
							break;
						}
					}
					if(!exist)
					{
						this->transitionList.push_back(t);
					}
				}
			}
		}
	}
	for(l = this->finishList.begin(); l != this->finishList.end(); l++)
	{
		for(i = this->transitionList.begin(); i != this->transitionList.end(); i++)
		{
			if(i->end == *l && i->symbol == '$')
			{
				this->finishList.push_back(i->begin);
				this->finishList.sort();
				break;
			}
		}
	}
	repeat = true;
	while(repeat)
	{
		repeat = false;
		for(i = this->transitionList.begin(); i != this->transitionList.end(); i++)
		{
			if(i->symbol == '$')
			{
				this->transitionList.erase(i);
				repeat = true;
				break;
			}
		}
	}
	this->symbolList.remove('$');
}

template <class Type>
list<string> NonFinAut<Type>::sort(list<string> &sourceList)
{
	list<string> resultList;
	list<string>::const_iterator i, j;
	sourceList.sort();
	sourceList.unique();
	for(i = sourceList.begin(); i != sourceList.end(); i++)
	{
		if(resultList.empty())
		{
			resultList.push_front(*i);
		}
		else
		{
			for(j = resultList.begin(); j != resultList.end(); j++)
			{
				if(j->length() > i->length())
				{
					break;
				}
			}
			resultList.insert(j, *i);
		}
	}
	return resultList;
}
template <class Type>
void NonFinAut<Type>::makeDrawning(NonFinAut<Type> &obj)
{
	//multimap<string, Transition<string>*> objTable = obj.getTransitionList();
    //multimap<string, Transition<string>*>::iterator itObj;
	list<Transition<Type>> objTable = obj.getTransitionList();
	list<Transition<Type>>::iterator itObj;
	list<Type> StartStates = obj.getStartList();
    list<Type>::iterator itStartStates;
	list<Type> EndStates = obj.getFinishList();
    list<Type>::iterator itEndStates;
    //string ErrorState = obj.getErrorState();
    ofstream myfile;
    myfile.open ("drawing");
    myfile << "digraph G { \n";
    bool combinedStartEnd=false;

    for (itEndStates=EndStates.begin(); itEndStates!=EndStates.end(); itEndStates++)
        myfile << *itEndStates << "[color=yellow style=filled]; \n";
//    if(ErrorState.length()>1)
  //      myfile << ErrorState << "[color=red style=filled]; \n";

    //kleuren van start/stop en error-states
    for (itStartStates=StartStates.begin(); itStartStates!=StartStates.end(); itStartStates++)
    {
        bool isEndState=false;
            for (itEndStates=EndStates.begin(); itEndStates!=EndStates.end(); itEndStates++)
            {
                if(*itStartStates==*itEndStates)
                {
                    //EndStates.erase(*itEndStates);
                    combinedStartEnd=true;
                    isEndState=true;
                    myfile << *itStartStates << "[color=green style=filled]; \n";
                    break;
                }

            }
            if(!isEndState)
                myfile << *itStartStates << "[color=blue style=filled]; \n";
    }


    //schrijven legenda!
    if(StartStates.size()>1)
        if(combinedStartEnd)
            myfile << "StartEndStates [shape = box color=green style=filled]; \n";
        else
            myfile << "StartStates [shape = box color=blue style=filled]; \n";
    else
        if(combinedStartEnd)
            myfile << "StartEndState [shape = box color=green style=filled]; \n";
        else
            myfile << "StartState [shape = box color=blue style=filled]; \n";
    if(EndStates.size()>1)
        myfile << "EndStates [shape = box color=yellow style=filled]; \n";
    else
        if(EndStates.size()==1)
            myfile << "EndState [shape = box color=yellow style=filled]; \n";
//    if(ErrorState.length()>1)
  //      myfile << "ErrorState [shape = box color=red style=filled]; \n";

    //schrijven states en transities
    for (itObj=objTable.begin(); itObj!=objTable.end(); itObj++)
		myfile << (*itObj).begin << "->" << (*itObj).end << "[taillabel=\"" << (*itObj).symbol << "\"]; \n";

    myfile << "} \n";
    myfile.close();
    //aanmaken drawing.png d.m.v. command line util
    system("dot -Kdot -Tpng -O drawing");
    //gebruik windows geregistreerde viewer voor png bestanden
    system("drawing.png");
}


//erbij voor thompson
template<class Type>
NonFinAut<Type>::NonFinAut(unsigned size_, state initial_, state final_)
	: size(size_), initial(initial_), final(final_)
{
    //assert(is_legal_state(initial));
	is_legal_state(initial);
    //assert(is_legal_state(final));
	is_legal_state(final);
    
	vector<input> empty_row(size, NONE);
	
    // Initialize trans_table with an "empty graph", no transitions
    // between its states
    //
    for (unsigned i = 0; i < size; ++i)
        trans_table.push_back(empty_row);
}

template<class Type>
NonFinAut<Type>& NonFinAut<Type>::operator=(const NonFinAut<Type>& other)
{
	if (this == &other)
		return *this;
	
	initial = other.initial;
	final = other.final;
	size = other.size;
	trans_table = other.trans_table;
	startList = other.startList;
	finishList = other.finishList;
	stateList = other.stateList;
	symbolList = other.symbolList;
	transitionList = other.transitionList;
	
	return *this;
}

template<class Type>
bool NonFinAut<Type>::is_legal_state(state s)
{
	// We have 'size' states, numbered 0 to size-1
	//
    if (s < 0 || s >= size)
        return false;
    
    return true;
}

template<class Type>
void NonFinAut<Type>::add_trans(state from, state to, input in)
{
    //assert(is_legal_state(from));
	is_legal_state(from);
    //assert(is_legal_state(to));
	is_legal_state(to);
    
    trans_table[from][to] = in;    
}

template<class Type>
void NonFinAut<Type>::shift_states(unsigned shift)
{
	unsigned new_size = size + shift;
	
	if (shift < 1)
		return;
	
	// create a new, empty transition table (of the new size)
	//
	vector<input> empty_row(new_size, NONE);
	vector<vector<input> > new_trans_table(new_size, empty_row);
	
	// copy all the transitions to the new table, at their
	// new locations
	//
	for (state i = 0; i < size; ++i)
	{
		for (state j = 0; j < size; ++j)
		{
			new_trans_table[i + shift][j + shift] = trans_table[i][j];
		}
	}
	
	// update the NFA members
	//
	size = new_size;
	initial += shift;
	final += shift;
	trans_table = new_trans_table;
}

template<class Type>
void NonFinAut<Type>::fill_states(const NonFinAut<Type>& other)
{
    for (state i = 0; i < other.size; ++i)
    {
        for (state j = 0; j < other.size; ++j)
        {
			trans_table[i][j] = other.trans_table[i][j];
		}
	}
}

template<class Type>
void NonFinAut<Type>::append_empty_state(void)
{
	// append a new row (already with a larger size)
	//
	vector<input> empty_row(size + 1, NONE);
	trans_table.push_back(empty_row);
	
	// append a new column
	//
	for (state i = 0; i < size; ++i)
		trans_table[i].push_back(NONE);
	
	size += 1;
}



template<class Type>
NonFinAut<Type> NonFinAut<Type>::show(NonFinAut<Type> &nfa)
{
	list<Type> begin, end;
	string q = getStateNr(initial);
	string y = getStateNr(final);;
	begin.push_back(q);
	end.push_back(y);
	NonFinAut<Type> nonFinAut(begin, end);
	    
    for (state from = 0; from < size; ++from)
    {
        for (state to = 0; to < size; ++to)
        {
            input in = trans_table[from][to];
			string g1 = getStateNr(from);
			string g2 = getStateNr(to);
            
            if (in != NONE)
            {
				if (in == EPS)
                {
					char g3 = EPS + 41;
                    nfa.addTransition(g1, '$', g2);
                }
                else
                {
					char g3 = in;
                    nfa.addTransition(g1, g3, g2);

                }
			}
				
        }
    }
	nfa.addStartState(q);
	nfa.addFinishState(y);
	return nfa;	
}

template<class Type> 
string NonFinAut<Type>::getStateNr(int nr)
{
	char prefix = 'q';
	stringstream stream;
	stream << prefix << nr;
	string resultString = stream.str();
	return resultString;
}